Transmission Control Protocol (TCP) is an Internet Engineering Task Force (IETF) protocol that operates at the Open Standards Interconnect (OSI) layer 4 and is used for the majority of host-to-host Internet applications such as FTP (File Transfer Protocol), HTTP (Hypertext Transfer Protocol), news, telnet and e-mail. A working group within IETF (Internet Engineering Task Force) does standardization work on TCP/IP, (IP meaning “Internet Protocol”) which is documented in “Requests for Comment” (RFC) numbers 793, 1122, 1146, 1644, 2018, 2581, 2861, 2883, 3168, 3390, 3517, 3540 and others.
TCP offers connection-orientated, guaranteed delivery of data using transmission sequence numbers that are positively acknowledged (ACK'd) by the receiving host (receiver). Flow control is performed via a sliding window mechanism; the receiver returns a “window” with every ACK indicating a range of acceptable sequence numbers beyond the last segment successfully received. The window indicates an allowed number of bytes that the sender may transmit into the network before receiving further permission.
Each TCP packet is accompanied by a sequence number, which is the packet's position in the sending host's (sender's) output buffer, measured in bytes from the beginning of the buffer, plus a random offset, which is chosen at the start of the connection to avoid simultaneous use of duplicate sequence number values.
If a sender doesn't receive an acknowledgment of a particular packet within a predetermined time (either because the packet never reached the receiver, or the ACK was never sent or because the ACK itself was lost), it automatically re-transmits the packet.
The Internet and its millions of users now depend upon the smooth operation of TCP. Clearly, some mechanism for large-scale monitoring of TCP would be extremely valuable in ensuring that performance is optimised, faults are easily identifiable, service level agreements are maintained by Internet Service Providers (ISPs), and end users can expect a guaranteed high quality of service.
There are, however, several difficulties when monitoring TCP flows. Firstly, the majority of flows are often short-lived, and secondly, there will be many millions of simultaneous concurrent active flows between the many hosts present on the Internet at any one time. Thus, any monitoring technique should be both simple and lightweight to implement. Furthermore, the implementation should preferably not consume costly resources and should be scaleable, so that it can be applied to many simultaneous concurrent flows and deployed in many places around the Internet without causing additional overhead itself.
Traditional measures used to monitor TCP performance include “Goodput”, which is the amount of data received versus the amount transmitted; the amount transmitted includes retransmissions caused by losses in the network. Goodput provides a simple method of indicating the ‘health’ of a TCP connection, as retransmissions are an excess overhead on the network that should be avoided.
Goodput measures the volume of all the transmitted TCP payloads in a given flow by recording the first and last sequence numbers for a given direction in a flow. This provides the amount of traffic successfully transmitted and received during the lifetime of that flow. The calculation is adjusted to make allowance for the SYN and FIN signalling packets that signal start and end of the flow and increase the sequence number without transmitting any payload.
The traditional goodput measurement does not provide any indication of the point at which the transmission breakdown may have occurred, nor the severity of the breakdown that was present at each event. Goodput also fails to provide any method for identifying the location in a flow where a retransmission has occurred, nor does it indicate whether this retransmission was as a result of one single large event or many small events. Without knowing the timing and severity of each event, it is impossible to gauge or estimate the actual impact upon an end-user, as different amounts of transmission breakdown will have varying levels of impact.
A single point measurement technique is desirable from a network monitoring perspective. The Internet promotes multi-path routing, which results in, for example, an asymmetry of TCP flows, where the outgoing data packets may choose a different route from the resulting Acknowledgement packets. Therefore, a single point measurement technique should allow measurement of both data and ACK packets at geographically separate points. Further, single point measurements have no requirement for time synchronisation between measurement probes. Similarly there are no requirements for computationally expensive and bandwidth intensive real-time correlation of measurement data between probes. Time synchronizing a large number of measurement devices over a very wide area, and to a high degree of accuracy, is costly and would significantly increase the purchase price of the end-device.
Thus, the ability to perform accurate single point measurement of TCP goodput, loss and retransmission over time can be a very useful tool in IP network management. Such a tool should preferably be scaleable, low cost and easy to deploy. Moreover, the results from a number of geographically diverse measurements can help determine the location of a fault or congestion, allowing remedial action to be taken. Similarly, results can be used to measure the level of service attributed to individual flows, since loss measurements are key to service level agreements.
It is worth noting that IP networks do not enforce any rules regarding packet order during transit. An IP router is free to forward a packet from a flow before it has completed forwarding all of that packet's predecessors. Unfortunately, for TCP, reordering events can appear as though a packet has been lost followed by its eventual retransmission, thereby rendering errors in many performance measurements.
The term ‘out-of-sequence packets’ is therefore used to indicate packets that arrive at the receiver, for whatever reason, out of order with respect to their original transmitted order at the sending host (sender). In TCP, out of sequence packets can be as a result of loss followed by retransmission or due to reordering at any intermediate element in the IP network. A flow with a large number of out-of-sequence packets, whatever the reason, is indicative of poor transmission characteristics and hence a poor user experience.
A conventional measure of TCP retransmission takes the sum of all the TCP packet lengths actually transmitted and subtracts the goodput figure giving a value for retransmitted packets. By making this measurement near the TCP source it produces an accurate measure of the retransmissions caused by packet loss ‘downstream’ from that point in the flow. However, if the measurement is made at a point where some packets may have already been lost, then the retransmission measurement will under report the value by the amount of the loss.
European Patent EP1111871 describes a mechanism for single point measurement of retransmission, loss, and goodput of TCP flows. For each TCP connection being monitored, a next expected sequence number value (NESN) is maintained and compared with the actual sequence number of a packet seen in that flow. If the sequence number is less than the NESN, a retransmission count is incremented by the size of the retransmitted TCP payload; if it is greater then the NESN, a loss counter is incremented by the size of the lost TCP payload.
The technique described in EP1111871, using analysis of the sequence numbers, enables an observer at an arbitrary monitoring point on a TCP connection to estimate the traffic that was originally sent by the transmitting node, even though some of this traffic may have already been lost. However, IP traffic is not guaranteed to arrive at the observation point in the order of transmission. Therefore out-of-sequence packets can be caused by loss followed by retransmission or packet reordering. Clearly, when taking measurements at the transmission source, before the packets traverse a switching device, no packet re-ordering can have occurred and the traditional calculation for retransmission based upon subtracting goodput from throughput will suffice. However, any measurements using this method at subsequent points in the network, after the packets have passed through one or more routers or switches, are likely to over estimate the amount of loss and retransmission by the amount of packet reordering that occurred.
Packet reordering can occur due to parallelism in the network, either at the link-level or switch level, or due to the dynamic nature of Internet routing. The most conservative study as disclosed in, “End-to-end Internet Packet Dynamics”, IEEE/ACM Transactions on Networking, Paxon, June 1999 shows between 0.03% and 0.78% of packets reordered with between 0.15% and 4.9% of flows being affected. However, in “Measurement and classification of Out-of-Sequence Packets in a Tier-1 IP Backbone”, Jaiswal et al; Proceedings of Internet Measurement Workshop, November 2002, noted much greater packet reordering probabilities of up to 5% of packets and 15% of flows affected. Preliminary research in “Packet Reordering is not Pathological Network Behaviour”, Bennett et al, IEEE/ACM Transactions on Networking, December 1999 shows that much of this parallelism can be attributed to modern router architectures that use massive parallelism to support multi-gigabit line rates over a number of interface cards, and to link-level parallelism or “striping”. It is often much cheaper, as well as offering a degree of redundancy, to install several slow links between a given source and destination than a single fast link.
The worst case flow examined in “Measurement and classification of Out-of-Sequence Packets in a Tier-1 IP Backbone”, exhibited 4.67% of all packets out-of-sequence with 16.70% of those out-of-sequence packets as actually being reordered. Recognizing that an out-of-sequence packet is either reordered or has simply been retransmitted due to a prior loss is key to eliminating reordered packets from the retransmission count. Reordered packets will not be retransmitted and will cause over-reading of both the loss and the retransmission counts. Moreover, below a certain threshold, where a retransmission is not triggered reordering will have less impact upon the end user's experience.
Full determination of the cause of an out-of-sequence arrival requires knowledge of whether a packet is late due to retransmission or is just reordered. TCP will retransmit a packet when either the current retransmission timeout (RTO) value at the sender has passed without it having received an acknowledgement for that packet, or, in more recent TCP implementations, when three successive duplicate acknowledgements have been seen at the sender, in a method known as “fast retransmission”.
In their paper, “Measurement and Classification of Out-of-Sequence packets in a Tier-1 IP Backbone”, Jaiswal et al. present a measurement study and classification methodology for out-of-sequence packets in TCP connections. Their work builds on that of Paxon, as described in his paper “End-to-end Internet Packet Dynamics”, IEEE/ACM Transactions on Networking, June 1999 and on that of Bennett et al, as described in their paper “Packet Reordering is not Pathological Network Behaviour”. Their aim was to classify the causes of out-of-sequence packets. By observing properties of the forward path packets carrying the TCP segments observed, such as time of observance, the packet's IP Identification field, the existence of the segments reverse path ACK packets, and some derived measures, such as the time difference between two occurrences of the same TCP segment, the presented methodology allows categorization of out of sequence packets into one of 5 types. These are; 1 “Retransmission”, 2 “Unneeded Retransmission”, 3 “Network Duplicate”, 4 “Reordering”, and 5 “Unknown”.
However, as part of their mechanism they rely on two things, among others, to allow their measurement to work. Namely, that they have to observe the return path ACK packets, and that they have an accurate estimation of the senders “round trip delay, RTT” and “retransmission timeout interval, RTO”. There are simply too many complex heuristics used in this method to make a simple, lightweight and reliable measurement. Moreover Jaiswal et al. found only approximately 13% of the monitored flows to be symmetrical, without the return path flow symmetry the remaining 87% of the captured flows could not be measured using their technique.
In the IP Performance Metrics Working Group's working paper “Reordering Metric for IPPM” Morton et al, (draft-ietf-ippm-reordering-10.txt) it is suggested that byte counts are used as sequence numbers to show transmission order. This is an on-the-fly method that uses next-expected-sequence numbers, rather like EP1111871, to recognise out-of-sequence packets. However, the use of packet byte counts makes it difficult to calculate the position of a packet in a stream on-the-fly without recording the size of the intervening packets. It is also suggested in the paper that packet sizes are stored, but no mechanism for calculating sequences when the intervening packets themselves are also reordered is offered.
Out-of-sequence packets in the reverse path, or acknowledgement path, also affect TCP transmission. Bennett et al describe in “Packet Reordering is not Pathological Network Behaviour”, how out-of-sequence packets in the acknowledge path cause TCP to loose its self-clocking property with forward path transmission becoming bursty, hence affecting data transmission.
In summary, several attempts have been made to offer an accurate single point measurement of loss, goodput and retransmission. None of these measurements, though, have been proven to be both accurate, to within acceptable tolerances, and be lightweight enough so that they can be run in real-time and for many concurrent flows.
The present invention therefore seeks to provide a method for real time monitoring of TCP flows, which overcomes, or at least reduces the above-mentioned problems of the prior art.